package algorithm.test1Tree.test3RevertTree;

import algorithm.test1Tree.test2BST.BinarySearchTree;
import algorithm.test1Tree.testOld.Tree;

import java.util.LinkedList;
import java.util.Queue;

public class RevertTree {
    /**
     * 前序遍历
     * 这个返回值表示翻转之后的根节点
     * @param root
     * @return
     */
    public TreeNode invertTree1(TreeNode root){
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        //由于上面交换了左右，所以这里的左其实是右，右其实是左，但是不影响
        invertTree1(root.left);
        invertTree1(root.right);
        return root;
    }

    /**
     * 后序遍历
     * @param root
     * @return
     */
    public TreeNode invertTree2(TreeNode root){
        if(root==null){
            return null;
        }
        //先访问左右，后访问自己
        invertTree2(root.left);
        invertTree2(root.right);


        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        return root;
    }

    /**
     * 中序遍历，其实就是访问打位置不同
     * @param root
     * @return
     */
    public TreeNode invertTree3(TreeNode root){
        if(root==null){
            return null;
        }

        invertTree3(root.left);

        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        //由于上面交换了左右，这里的left其实就是right
        invertTree3(root.left);

        return root;
    }

    /**
     * 层序遍历
     * @param root
     * @return
     */
    public TreeNode invertTree4(TreeNode root){
        if(root==null){
            return null;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();//头节点出队
            TreeNode tmp=node.left;
            node.left=root.right;
            node.right=tmp;

            if(node.left !=null){
                queue.offer(node.left);
            }
            if(node.right !=null){
                queue.offer(node.right);
            }
        }
        return root;
    }

}
